package algorithm.middle;

import java.util.ArrayList;

/**
 * 给定一个表示分数加减运算的字符串 expression ，你需要返回一个字符串形式的计算结果。 
 * <p>
 * 这个结果应该是不可约分的分数，即最简分数。 如果最终结果是一个整数，例如 2，你需要将它转换成分数形式，其分母为 1。所以在上述例子中, 2 应该被转换为 2/1。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/fraction-addition-and-subtraction
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class FractionAddition592 {

    public String fractionAddition(String expression) {
        /*
         * 便于处理
         * -1/2+1/2-1/3 => +-1/2+1/2+-1/3 => -1/2+1/2+-1/3
         * [-1/2,1/2,-1/3]
         */
        expression = expression.replace("-", "+-");
        if (expression.charAt(0)=='+'){
            expression = expression.substring(1);
        }
        Fraction fraction = new Fraction(0, 1);
        String[] split = expression.split("\\+");
        for (String item:split){
            int i = item.indexOf('/');
            String numString = item.substring(0, i);
            String denString = item.substring(i+1);
            fraction = Fraction.add(fraction, new Fraction(Integer.parseInt(numString), Integer.parseInt(denString)));
        }
        return fraction.toString();
    }

    /**
     * 分数类
     */
    public static class Fraction {
        //分子
        int numerator;

        //分母
        int denominator;

        public Fraction(int numerator, int denominator) {
            this.numerator = numerator;
            this.denominator = denominator;
        }

        public Fraction() {
        }

        public static Fraction add(Fraction a, Fraction b){
            long numerator = a.numerator * b.denominator + b.numerator * a.denominator;
            long denominator = a.denominator * b.denominator;
            //返回分数形式的0
            if (numerator ==0) {
                return new Fraction(0,1);
            }
            long gcd = gcd(numerator, denominator);
            return new Fraction((int) (numerator / gcd), (int) (denominator / gcd));

        }

        //最大公约数
        private static long gcd(long a, long b) {
            return b == 0 ? a : gcd(b, a % b);
        }

        @Override
        public String toString() {
            if (denominator<0){
                numerator = -numerator;
                denominator = -denominator;
            }
            return numerator + "/" + denominator;
        }


    }



    public static void main(String[] args) {
        System.out.println(new FractionAddition592().fractionAddition("-1/2+1/2+1/3"));
        System.out.println(new FractionAddition592().fractionAddition("1/3-1/2"));
    }
}
